{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 高阶函数\n",
    "高阶函数英文叫Higher-order function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 变量可指向函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function abs(x, /)>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 函数本身可以赋值给变量\n",
    "f = abs\n",
    "f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 如果一个变量指向了一个函数，可通过该变量来调用这个函数\n",
    "f = abs\n",
    "f(-10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 函数名也是变量\n",
    "\n",
    "那么函数名是什么呢？函数名其实就是指向函数的变量！对于abs()这个函数，完全可以把函数名abs看成变量，它指向一个可以计算绝对值的函数！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 传入函数\n",
    "\n",
    "既然变量可以指向函数，函数的参数能接收变量，那么一个函数就可以接收另一个函数作为参数，这种函数就称之为高阶函数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n        推导计算过程：\\n        x = -5\\n        y = 6\\n        f = abs\\n        f(x) + f(y) ==> abs(-5) + abs(6) ==> 11\\n        return 11\\n'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "        推导计算过程：\n",
    "        x = -5\n",
    "        y = 6\n",
    "        f = abs\n",
    "        f(x) + f(y) ==> abs(-5) + abs(6) ==> 11\n",
    "        return 11\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11\n"
     ]
    }
   ],
   "source": [
    "# 一个简单的高阶函数：\n",
    "def add(x, y, f):\n",
    "    return f(x) + f(y)\n",
    "print(add(-5, 6, abs))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "把函数作为参数传入，这样的函数称为高阶函数，函数式编程就是指这种高度抽象的编程范式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## map()和reduce()函数\n",
    "\n",
    "关于map/reduce的概念：参见Google的那篇大名鼎鼎的论文“MapReduce: Simplified Data Processing on Large Clusters”"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- map\n",
    "\n",
    "我们先看map。map()函数接收两个参数，一个是函数，一个是Iterable，map将传入的函数依次作用到序列的每个元素，并把结果作为新的Iterator返回。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 9, 16, 25, 36, 49, 64, 81]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 一个函数f(x) = x*x, 把这个函数作用在list[1, 2, 3, 4, 5, 6, 7, 8 ,9]上\n",
    "# 用Python代码实现\n",
    "def f(x):\n",
    "    return x * x\n",
    "r = map(f, [1, 2, 3, 4, 5, 6, 7, 8, 9])\n",
    "list(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 4, 9, 16, 25, 36, 49, 64, 81]\n"
     ]
    }
   ],
   "source": [
    "# 循环实现\n",
    "L = []\n",
    "for n in [1, 2, 3, 4, 5, 6, 7, 8, 9]:\n",
    "    L.append(f(n))\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面对比，可知map()作为高阶函数，事实上它把运算规则抽象了，因此，我们不但可以计算简单的f(x)=x2，还可以计算任意复杂的函数，比如，把这个list所有数字转为字符串："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '2', '3', '4', '5', '6', '7', '8', '9']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 把这个list所有数字转为字符串\n",
    "list(map(str, [1, 2, 3, 4, 5, 6, 7, 8, 9]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- reduce\n",
    "\n",
    "reduce把一个函数作用在一个序列[x1,  x2,  x3, ...]上，这个函数必须接收两个参数，reduce把结果继续和序列的下一个元素做累积计算，其效果就是：\n",
    "\n",
    "            reduce(f, [x1, x2, x3, x4]) = f(f(f(x1, x2), x3), x4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 案例：\n",
    "# 对一个序列求和\n",
    "from functools import reduce\n",
    "def add(x, y):\n",
    "    return x + y\n",
    "reduce(add, [1, 2, 3 ,3, 9])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13579"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 把序列[1, 3, 5, 7, 9]变换成整数13579，\n",
    "from functools import reduce\n",
    "def fn(x, y):\n",
    "    return x * 10 + y\n",
    "reduce(fn, [1, 3, 5, 7, 9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "考虑到字符串str也是一个序列，对上面的例子稍加改动，配合map()，我们就可以写出把str转换为int的函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13579"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from functools import reduce\n",
    "def fn(x, y):\n",
    "    return x * 10 + y\n",
    "\n",
    "def char2num(s):\n",
    "    digits = {'0': 0, '1':1 , '2': 2,'3': 3, '4': 4, '5': 5,'6': 6, '7': 7, '8': 8, '9': 9}\n",
    "    return digits[s]\n",
    "\n",
    "reduce(fn, map(char2num, '13579'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 整理成一个str2int的函数\n",
    "from functools import reduce\n",
    "\n",
    "DIGITS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}\n",
    "\n",
    "def str2int(s):\n",
    "    def fn(x, y):\n",
    "        return x * 10 + y\n",
    "    def char2num(s):\n",
    "        return DIGITS[s]\n",
    "    return reduce(fn, map(char2num, s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 用lambda函数进一步简化成\n",
    "from functools import reduce\n",
    "\n",
    "DIGITS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}\n",
    "\n",
    "def char2num(s):\n",
    "    return DIGITS[s]\n",
    "\n",
    "def str2int(s):\n",
    "    return reduce(lambda x, y: x * 10 + y, map(char2num, s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 练习\n",
    "利用map()函数，把用户输入的不规范的英文名字，变为首字母大写，其他小写的规范名字。输入：['adam', 'LISA', 'barT']，输出：['Adam', 'Lisa', 'Bart']："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Adam', 'Lisa', 'Bart']\n"
     ]
    }
   ],
   "source": [
    "def normalize(name):\n",
    "    name = name[0].upper() + name[1:].lower()\n",
    "    return name\n",
    "\n",
    "L1 = ['adam', 'LISA', 'barT']\n",
    "L2 = list(map(normalize, L1))\n",
    "print(L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python提供的sum()函数可以接受一个list并求和，请编写一个prod()函数，可以接受一个list并利用reduce()求积："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 * 5 * 7 * 9 = 945\n",
      "测试成功!\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "def prod(L):\n",
    "    def f(x, y):\n",
    "        return x * y\n",
    "    return reduce(f, L)\n",
    "\n",
    "print('3 * 5 * 7 * 9 =', prod([3, 5, 7, 9]))\n",
    "if prod([3, 5, 7, 9]) == 945:\n",
    "    print('测试成功!')\n",
    "else:\n",
    "    print('测试失败!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "利用map和reduce编写一个str2float函数，把字符串'123.456'转换成浮点数123.456："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "str2float('123.456') = 123.456\n",
      "测试成功!\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    " \n",
    "def str2float(s):\n",
    "    def fn(x, y):\n",
    "        return x * 10 + y\n",
    "    def char2num(s):\n",
    "        return {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}[s]\n",
    "    \n",
    "    # 得到字符串中.的索引\n",
    "    n = s.index('.')\n",
    "    \n",
    "    # 根据.的位置将字符串切片为两段\n",
    "    s1 = list(map(int, [x for x in s[: n]]))\n",
    "    s2 = list(map(int, [x for x in s[n + 1 :]]))\n",
    "    \n",
    "    # m ** n表示m的n次方\n",
    "    return reduce(fn, s1) + reduce(fn, s2) / 10 ** len(s2)\n",
    "\n",
    "# 测试：\n",
    "print('str2float(\\'123.456\\') =', str2float('123.456'))\n",
    "if abs(str2float('123.456') - 123.456) < 0.00001:\n",
    "    print('测试成功!')\n",
    "else:\n",
    "    print('测试失败!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "str2float('123.456') = 123.456\n",
      "测试成功!\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "DIGITS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}\n",
    "\n",
    "def str2float(s):\n",
    "        def fn(x, y):\n",
    "            return x * 10 + y\n",
    "        def char2num(s):\n",
    "            return DIGIYS[s]\n",
    "        \n",
    "        n = s.index('.')\n",
    "        s1 = list(map(int, [x for x in s[: n]]))\n",
    "        s2 = list(map(int, [x for x in s[n + 1 :]]))\n",
    "        return reduce(fn, s1) + reduce(fn, s2)/10 ** len(s2)\n",
    "    \n",
    "# 测试：\n",
    "print('str2float(\\'123.456\\') =', str2float('123.456'))\n",
    "if abs(str2float('123.456') - 123.456) < 0.00001:\n",
    "    print('测试成功!')\n",
    "else:\n",
    "    print('测试失败!')\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## filter\n",
    "\n",
    "Python内建的filter()函数用于过滤序列。\n",
    "\n",
    "和map()类似，filter()也接收一个函数和一个序列。和map()不同的是，filter()把传入的函数依次作用于每个元素，然后根据返回值是True还是False决定保留还是丢弃该元素。\n",
    "\n",
    "例如，在一个list中，删掉偶数，只保留奇数，可以这么写："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 5, 9, 15]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def is_odd(n):\n",
    "    return n % 2 == 1\n",
    "\n",
    "list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "把一个序列中的空字符串删掉:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'C']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def not_empty(s):\n",
    "    return s and s.strip()\n",
    "\n",
    "list(filter(not_empty, ['A', '', 'B', None, 'C', '  ']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 用filter求素数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计算素数的一个方法是埃氏筛法，它的算法理解起来非常简单：\n",
    "\n",
    "首先，列出从2开始的所有自然数，构造一个序列：\n",
    "\n",
    "2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\n",
    "\n",
    "取序列的第一个数2，它一定是素数，然后用2把序列的2的倍数筛掉：\n",
    "\n",
    "3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\n",
    "\n",
    "取新序列的第一个数3，它一定是素数，然后用3把序列的3的倍数筛掉：\n",
    "\n",
    "5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\n",
    "\n",
    "取新序列的第一个数5，然后用5把序列的5的倍数筛掉：\n",
    "\n",
    "7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...\n",
    "\n",
    "不断筛下去，就可以得到所有的素数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 先构造一个从3开始的奇数序列:\n",
    "# 这是一个生成器，并且是一个无限序列\n",
    "def _odd_iter():\n",
    "    n = 1\n",
    "    while True:\n",
    "        n = n + 2\n",
    "        yield n\n",
    "        \n",
    "# 然后定义一个筛选函数:\n",
    "def _not_divisible(n):\n",
    "    return lambda x: x % n > 0\n",
    "\n",
    "# 定义一个生成器，不断返回下一个素数：\n",
    "def primes():\n",
    "    yield 2\n",
    "    it = _odd_iter() # 初始序列\n",
    "    while True:\n",
    "        n = next(it) # 返回序列的第一个数\n",
    "        yield n\n",
    "        it = filter(_not_divisible(n), it) # 构造新序列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "7\n",
      "11\n",
      "13\n",
      "17\n",
      "19\n",
      "23\n",
      "29\n",
      "31\n",
      "37\n",
      "41\n",
      "43\n",
      "47\n",
      "53\n",
      "59\n",
      "61\n",
      "67\n",
      "71\n",
      "73\n",
      "79\n",
      "83\n",
      "89\n",
      "97\n",
      "101\n",
      "103\n",
      "107\n",
      "109\n",
      "113\n",
      "127\n",
      "131\n",
      "137\n",
      "139\n",
      "149\n",
      "151\n",
      "157\n",
      "163\n",
      "167\n",
      "173\n",
      "179\n",
      "181\n",
      "191\n",
      "193\n",
      "197\n",
      "199\n",
      "211\n",
      "223\n",
      "227\n",
      "229\n",
      "233\n",
      "239\n",
      "241\n",
      "251\n",
      "257\n",
      "263\n",
      "269\n",
      "271\n",
      "277\n",
      "281\n",
      "283\n",
      "293\n",
      "307\n",
      "311\n",
      "313\n",
      "317\n",
      "331\n",
      "337\n",
      "347\n",
      "349\n",
      "353\n",
      "359\n",
      "367\n",
      "373\n",
      "379\n",
      "383\n",
      "389\n",
      "397\n",
      "401\n",
      "409\n",
      "419\n",
      "421\n",
      "431\n",
      "433\n",
      "439\n",
      "443\n",
      "449\n",
      "457\n",
      "461\n",
      "463\n",
      "467\n",
      "479\n",
      "487\n",
      "491\n",
      "499\n",
      "503\n",
      "509\n",
      "521\n",
      "523\n",
      "541\n",
      "547\n",
      "557\n",
      "563\n",
      "569\n",
      "571\n",
      "577\n",
      "587\n",
      "593\n",
      "599\n",
      "601\n",
      "607\n",
      "613\n",
      "617\n",
      "619\n",
      "631\n",
      "641\n",
      "643\n",
      "647\n",
      "653\n",
      "659\n",
      "661\n",
      "673\n",
      "677\n",
      "683\n",
      "691\n",
      "701\n",
      "709\n",
      "719\n",
      "727\n",
      "733\n",
      "739\n",
      "743\n",
      "751\n",
      "757\n",
      "761\n",
      "769\n",
      "773\n",
      "787\n",
      "797\n",
      "809\n",
      "811\n",
      "821\n",
      "823\n",
      "827\n",
      "829\n",
      "839\n",
      "853\n",
      "857\n",
      "859\n",
      "863\n",
      "877\n",
      "881\n",
      "883\n",
      "887\n",
      "907\n",
      "911\n",
      "919\n",
      "929\n",
      "937\n",
      "941\n",
      "947\n",
      "953\n",
      "967\n",
      "971\n",
      "977\n",
      "983\n",
      "991\n",
      "997\n"
     ]
    }
   ],
   "source": [
    "# 打印1000以内的素数:\n",
    "for n in primes():\n",
    "    if n < 1000:\n",
    "        print(n)\n",
    "    else:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 练习\n",
    "回数是指从左向右读和从右向左读都是一样的数，例如12321，909。请利用filter()筛选出回数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1~1000: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383, 393, 404, 414, 424, 434, 444, 454, 464, 474, 484, 494, 505, 515, 525, 535, 545, 555, 565, 575, 585, 595, 606, 616, 626, 636, 646, 656, 666, 676, 686, 696, 707, 717, 727, 737, 747, 757, 767, 777, 787, 797, 808, 818, 828, 838, 848, 858, 868, 878, 888, 898, 909, 919, 929, 939, 949, 959, 969, 979, 989, 999]\n",
      "测试成功!\n"
     ]
    }
   ],
   "source": [
    "#方案一:\n",
    "def is_palindrome(n):\n",
    "    nn = str(n) # 转成字符串\n",
    "    return nn == nn[::-1] # 反转字符串并对比原字符串返回true/false\n",
    "\n",
    "# 测试:\n",
    "output = filter(is_palindrome, range(1, 1000))\n",
    "print('1~1000:', list(output))\n",
    "if list(filter(is_palindrome, range(1, 200))) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191]:\n",
    "    print('测试成功!')\n",
    "else:\n",
    "    print('测试失败!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1~1000: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383, 393, 404, 414, 424, 434, 444, 454, 464, 474, 484, 494, 505, 515, 525, 535, 545, 555, 565, 575, 585, 595, 606, 616, 626, 636, 646, 656, 666, 676, 686, 696, 707, 717, 727, 737, 747, 757, 767, 777, 787, 797, 808, 818, 828, 838, 848, 858, 868, 878, 888, 898, 909, 919, 929, 939, 949, 959, 969, 979, 989, 999]\n",
      "测试成功!\n"
     ]
    }
   ],
   "source": [
    "#方案二: filter(lambda n : str(n)==str(n)[::-1], range(1,1000))\n",
    "\n",
    "# 测试:\n",
    "output = filter(lambda n : str(n)==str(n)[::-1], range(1,1000))\n",
    "\n",
    "print('1~1000:', list(output))\n",
    "if list(filter(lambda n : str(n)==str(n)[::-1], range(1, 200))) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191]:\n",
    "    print('测试成功!')\n",
    "else:\n",
    "    print('测试失败!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1~1000: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383, 393, 404, 414, 424, 434, 444, 454, 464, 474, 484, 494, 505, 515, 525, 535, 545, 555, 565, 575, 585, 595, 606, 616, 626, 636, 646, 656, 666, 676, 686, 696, 707, 717, 727, 737, 747, 757, 767, 777, 787, 797, 808, 818, 828, 838, 848, 858, 868, 878, 888, 898, 909, 919, 929, 939, 949, 959, 969, 979, 989, 999]\n",
      "测试成功!\n"
     ]
    }
   ],
   "source": [
    "#方案三：\n",
    "def is_palindrome(n):\n",
    "      s = str(n)\n",
    "      h = list(range((len(s))//2))\n",
    "      for i in h:\n",
    "          if s[i] != s[-(i+1)]:\n",
    "             return False\n",
    "      return True\n",
    "\n",
    "# 测试:\n",
    "output = filter(is_palindrome, range(1, 1000))\n",
    "print('1~1000:', list(output))\n",
    "if list(filter(is_palindrome, range(1, 200))) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191]:\n",
    "    print('测试成功!')\n",
    "else:\n",
    "    print('测试失败!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## sorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 排序算法\n",
    "\n",
    "排序也是在程序中经常用到的算法。无论使用冒泡排序还是快速排序，排序的核心是比较两个元素的大小。如果是数字，我们可以直接比较，但如果是字符串或者两个dict呢？直接比较数学上的大小是没有意义的，因此，比较的过程必须通过函数抽象出来。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on built-in function sorted in module builtins:\n",
      "\n",
      "sorted(iterable, /, *, key=None, reverse=False)\n",
      "    Return a new list containing all items from the iterable in ascending order.\n",
      "    \n",
      "    A custom key function can be supplied to customize the sort order, and the\n",
      "    reverse flag can be set to request the result in descending order.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(sorted)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-21, -12, 5, 9, 36]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# sorted()函数就可以对list进行排序：\n",
    "sorted([36, 5, -12, 9, -21])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 9, -12, -21, 36]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 接收一个key函数来实现自定义的排序\n",
    "# 例如按绝对值大小排序：\n",
    "sorted([36, 5, -12, 9, -21], key = abs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['about', 'bob', 'Credit', 'Zoo']"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 忽略大小写的排序：\n",
    "sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Zoo', 'Credit', 'bob', 'about']"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 反向排序（降序），传入第三个参数reverse=True：\n",
    "sorted(['bob', 'about', 'Zoo', 'Credit'], key=str.lower, reverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 练习\n",
    "假设我们用一组tuple表示学生名字和成绩："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [('Bob', 75), ('Adam', 92), ('Bart', 66), ('Lisa', 88)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('Adam', 92), ('Bart', 66), ('Bob', 75), ('Lisa', 88)]\n"
     ]
    }
   ],
   "source": [
    "# 用sorted()对上述列表分别按名字排序：\n",
    "def by_name(t):\n",
    "    return t[0]\n",
    "L1 = sorted(L, key = by_name)\n",
    "print(L1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('Bart', 66), ('Bob', 75), ('Lisa', 88), ('Adam', 92)]\n"
     ]
    }
   ],
   "source": [
    "# 按成绩从高到低排序:\n",
    "def by_score(t):\n",
    "    return t[1]\n",
    "L2 = sorted(L, key = by_score)\n",
    "print(L2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
